/* http://shootout.alioth.debian.org/u32q/benchmark.php?test=pidigits&lang=gcc&id=4 */
/* The Computer Language Benchmarks Game
  http://shootout.alioth.debian.org/

  contributed by Paolo Bonzini & Sean Bartlett
  modified by Michael Mellor
*/

/* based on the C sample */

auto n = 27;
auto numer, accum, denom, tmp1, tmp2;

auto extract_digit() {
    if (numer > accum)
	return -1;

    /* Compute (numer * 3 + accum) / denom */
    tmp1 = ((numer << 1) + numer) + accum;
    tmp2 = tmp1 % denom;
    tmp1 = tmp1 \ denom;

    /* Now, if (numer * 4 + accum) % denom... */
    tmp2 += numer;

    /* ... is normalized, then the two divisions have the same result.  */
    if (tmp2 >= denom)
	return -1;

    return tmp1;
}

void next_term(k) {
    auto y2 = k * 2 + 1;

    accum += numer << 1;
    accum *= y2;
    numer *= k;
    denom *= y2;
}

void eliminate_digit(d) {
    accum -= denom * d;
    accum *= 10;
    numer *= 10;
}

void pidigits(n)
{
    auto d;
    auto i = 0, k = 0, m;

    tmp1 = tmp2 = accum = 0;
    numer = denom = 1;

    for (;;) {
	do {
	    ++k;
	    next_term(k);
	    d = extract_digit();
	} while(d == -1);

	print("%c", d + '0');

	++i;
	if ((m = i % 10) == 0)
	    print("\t:%d\n", i);
	if (i >= n)
	    break;
	eliminate_digit(d);
    }

    if (m) {
	m = 10 - m;
	while (m--)
	    print(" ");
	print("\t:%d\n", n);
    }
}

pidigits(n);
